# -*- coding: utf-8 -*-
# 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

# 每行中的整数从左到右按升序排列。
# 每行的第一个整数大于前一行的最后一个整数。
#  

# 示例 1：
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# 输出：true

# 示例 2：
# 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
# 输出：false 

# 提示：
# m == matrix.length
# n == matrix[i].length
# 1 <= m, n <= 100
# -104 <= matrix[i][j], target <= 104

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        row = len(matrix)
        col = len(matrix[0])
        cnt = row * col
        first = 0
        last = cnt - 1
        while first <= last:
            center = (first + last) // 2
            print([first, last, center])
            r = center // col
            c = center % col
            if matrix[r][c] == target:
                return True
            if matrix[r][c] < target:
                first = center + 1
            else:
                last = center - 1
        return False

t = Solution()
print(t.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 34))